package com.wrial.kind.tree;
/*
 * @Author  Wrial
 * @Date Created in 22:04 2020/8/17
 * @Description 判断是否为平衡二叉树
 */

public class IsBalanced {

    /**
     * 1.使用暴力递归判断(判断当前高度差的同时还需要保证子节点也是平衡的，如此递归下去)
     * 2.带有剪枝的递归
     *
     * @param root
     * @return
     */
//    public boolean isBalanced(TreeNode root) {
//        if (root == null) return true;
//        return Math.abs(height(root.left) - height(root.right)) < 2 && isBalanced(root.left) && isBalanced(root.right);
//    }
//
//    private int height(TreeNode root) {
//        if (root == null) return 0;
//        return Math.max(height(root.right), height(root.left)) + 1;
//    }
    public boolean isBalanced(TreeNode root) {
        return recur(root) != -1;
    }

    private int recur(TreeNode root) {
        if (root == null) return 0;
        int left = recur(root.left);
        if (left==-1) return -1;
        int right = recur(root.right);
        if (right==-1) return -1;
        return Math.abs(left - right) < 2 ? Math.max(right, left) + 1 : -1;
    }


    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
}